package first.codeTop.byteDance;

import java.util.HashMap;

/**
 * @ClassName Leetcode146
 * @description:
 * @author: 荣燊
 * @create: 2021-07-24 14:48
 **/
public class LRUCache {
    // Leetcode146，LRU 缓存机制，最近最少使用Least Recently Used
    // 新建链表的数据结构,双链表
    static class DLinkNode {
        int key;
        int val;
        DLinkNode pre;
        DLinkNode next;
        public DLinkNode() {
        }
        public DLinkNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    // cache，能够保证get操作是否能快速找到节点
    private static HashMap<Integer, DLinkNode> cache = new HashMap<>();
    // 记录cache中元素个数
    private static int size;
    // cache的最大容量
    private static int capacity;
    // 伪头结点和伪尾节点
    private static DLinkNode head;
    private static DLinkNode tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkNode();
        tail = new DLinkNode();
        head.next = tail;
        tail.pre = head;
    }

    public static int get(int key) {
        // 先使用cache进行快速定位
        DLinkNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 那么这是最近使用的
        moveToHead(node);
        return node.val;
    }

    public static void put(int key, int value) {
        DLinkNode node = cache.get(key);
        if (node == null) {
            // 不存在cache中，那么就新建一个，头插法
            DLinkNode dLinkNode = new DLinkNode(key, value);
            cache.put(key, dLinkNode);
            addToHead(dLinkNode);
            ++size;
            // 超过容量就删除尾部节点
            if (size > capacity) {
                DLinkNode dLinkNode1 = removeTail();
                cache.remove(dLinkNode1);
                --size;
            }
        } else {
            // 如果已经存在，查看value值需不需要修改
            node.val = value;
            moveToHead(node);
        }
    }

    // 除了以上方法，还需要重写几个方法
    // 方法1：头插法添加节点
    private static void addToHead(DLinkNode node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    // 方法2：删除某个节点
    private static void removeNode(DLinkNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    // 方法3：超过容量，应删除尾部节点,返回节点，便于从cache中删除
    private static DLinkNode removeTail() {
        DLinkNode res = tail.pre;
        removeNode(res);
        return res;
    }

    // 方法4：添加重复节点，应将节点移动到头部
    private static void moveToHead(DLinkNode node) {
        removeNode(node);
        addToHead(node);
    }
}
